import java.util.BitSet;


public class SnapShotStack {
	
	private static final int BITSTREAMHEIGHT =1000;
	private int numOfSnapShots = 0;
	
	private BitSet[][] boardSnapShots;
	private boolean[][] boardTagMatrix;
	private SnapShotStack nextSnapShotStack = null;	
	private BoardState[] boardStates;
	
	
	public boolean[][] getBoardTagMatrix() {
		return boardTagMatrix;
	}

	public void setBoardTagMatrix(boolean[][] boardTagMatrix) {
		this.boardTagMatrix = boardTagMatrix;
	}

	public void setNextSnapShotStack(SnapShotStack nextStack) {
		this.nextSnapShotStack = nextStack;
	}
	
	public SnapShotStack() {
		numOfSnapShots = 0;
		StaticMap globalMap = StaticMap.getStaticMap();
		boardStates = new BoardState[BITSTREAMHEIGHT];
		
		boardSnapShots = new BitSet[globalMap.boardW][globalMap.boardH];
		boardTagMatrix = new boolean[globalMap.boardW][globalMap.boardH];
		
		for (int i=0; i<globalMap.boardW ; i++) {
			for (int j=0; j<globalMap.boardH ; j++) {
				if (globalMap.isTileEmpty(i,j)) {
					
					boardSnapShots[i][j] = new BitSet(BITSTREAMHEIGHT);
					boardTagMatrix[i][j] = false;
				}
			}
		}
	}
	int c=0;
	
	public void addSnapshot(BoardState state) {
		if (nextSnapShotStack != null) {
			//TODO important!!! This is very slow, adding it at the end
			nextSnapShotStack.addSnapshot(state);
		} else if (numOfSnapShots == BITSTREAMHEIGHT) {
			numOfSnapShots++;
			nextSnapShotStack = new SnapShotStack();
			nextSnapShotStack.addSnapshot(state);
		} else if (numOfSnapShots < BITSTREAMHEIGHT) {		
			BoxList boxList = state.getBoxList();
			
			for(Box box : boxList) {
				Coord c = box.getCoord();
				boardSnapShots[c.x][c.y].set(numOfSnapShots);
				boardTagMatrix[c.x][c.y] = true;
			}

			boardStates[numOfSnapShots] = state;
			
			numOfSnapShots++;
		}
	}
	
	public void addSnapshotNaive(BoardState state) {
		if (numOfSnapShots < BITSTREAMHEIGHT) {		
			BoxList boxList = state.getBoxList();
			
			for(Box box : boxList) {
				Coord c = box.getCoord();
				boardSnapShots[c.x][c.y].set(numOfSnapShots);
				boardTagMatrix[c.x][c.y] = true;
			}

			boardStates[numOfSnapShots] = state;
			
			numOfSnapShots++;
		} else {
			System.err.println("Error: Tried to add snapshot to a saturated stack");
		}
	}
	
	public BoardState retrieveStateInCollection(BoardState state) {
		//System.out.println("diving========================");

		BoxList boxList = state.getBoxList();
		
		BitSet bitStreamCollector = null;
		Coord c = null;
		
		//Check for NEGATIVE in BoardTagMatrix.
		//False positives are possible.
		for(Box box : boxList) {
			c = box.getCoord();
			if (!boardTagMatrix[c.x][c.y]) {
				//Not here, check next board
				SnapShotStack nextStack = nextSnapShotStack;
				if (nextStack == null)
					return null;
				return (nextStack.retrieveStateInCollection(state));
			}
		}

		
		bitStreamCollector = (BitSet)boardSnapShots[c.x][c.y].clone();
		
		//Check the BitStreams. False positives are NOT possible.
		for(Box box : boxList) {
			c = box.getCoord();
			
			BitSet currentBitSet = boardSnapShots[c.x][c.y];
			bitStreamCollector.and(currentBitSet);			
		}
		
		int indexOfPositiveSnapShot = bitStreamCollector.nextSetBit(0);
		while (indexOfPositiveSnapShot != -1) {
			Coord playerPos = boardStates[indexOfPositiveSnapShot].getPlayerPos();
			
			if (DirectionMap.getDTile(playerPos).isVisited()) {		
				//boardStates[indexOfPositiveSnapShot].copyBoxList(state.getBoxList());
				return boardStates[indexOfPositiveSnapShot];
			}
			indexOfPositiveSnapShot = bitStreamCollector.nextSetBit(indexOfPositiveSnapShot+1);
		}
		
		SnapShotStack nextStack = nextSnapShotStack;
		if (nextStack == null)
			return null;
		
		return (nextStack.retrieveStateInCollection(state));

	}
	
	
	
	
	public SnapShotStack getNextSnapShotStack() {
		return nextSnapShotStack;
	}
	
	
	
	public BoardState retrieveStateInCollectionFast(BoardState state) {
		//System.out.println("diving========================");

		BoxList boxList = state.getBoxList();
		
		BitSet bitStreamCollector = null;
		Coord c = null;
		
		SnapShotStack currentStack = this;
		
		while(currentStack != null) {
		
		
			//===============================================
			//Tag check
			//===============================================
			boolean tagCheck = true;
			
			//Check for NEGATIVE in BoardTagMatrix.
			//False positives are possible.
			
			boolean[][] currentTagMatrix = currentStack.getBoardTagMatrix();
			
			for(Box box : boxList) {
				c = box.getCoord();
				if (!currentTagMatrix[c.x][c.y]) {
					//Not here, check next board
					SnapShotStack nextStack = currentStack.getNextSnapShotStack();
					if (nextStack == null)
						return null;
					
					currentStack = nextStack;
					tagCheck = false;
				}
			}
	
			if (tagCheck) {
				//===============================================
				//Search for repeated state in stack
				//===============================================
				
				bitStreamCollector = currentStack.cloneBitSet(c);
				
				//Check the BitStreams. False positives are NOT possible.
				for(Box box : boxList) {
					c = box.getCoord();
					
					BitSet currentBitSet = currentStack.getBitSet(c);
					bitStreamCollector.and(currentBitSet);			
				}
				
				int indexOfPositiveSnapShot = bitStreamCollector.nextSetBit(0);
				while (indexOfPositiveSnapShot != -1) {
					Coord playerPos = currentStack.getPlayerPos(indexOfPositiveSnapShot);
					
					if (DirectionMap.getDTile(playerPos).isVisited()) {		
						//boardStates[indexOfPositiveSnapShot].copyBoxList(state.getBoxList());
						return currentStack.getBoardState(indexOfPositiveSnapShot);
					}
					indexOfPositiveSnapShot = bitStreamCollector.nextSetBit(indexOfPositiveSnapShot+1);
				}
				
				SnapShotStack nextStack = currentStack.getNextSnapShotStack();
				if (nextStack == null)
					return null;
				
				currentStack = nextStack;
			}
		}
		return null;

	}
	
	public BoardState getBoardState(int index) {
		return boardStates[index];
	}
	
	public Coord getPlayerPos(int index) {
		return boardStates[index].getPlayerPos();
	}
	
	public BitSet getBitSet(Coord c) {
		return boardSnapShots[c.x][c.y];
	}
	
	public BitSet cloneBitSet(Coord c) {
		return (BitSet)boardSnapShots[c.x][c.y].clone();
	}
	
	
	
	
	
	
	
	
	
	
	
	
	public boolean isStackFull() {
		return (numOfSnapShots >= BITSTREAMHEIGHT);
	}
	
	public boolean isStateInCollection(BoardState state) {
		return (retrieveStateInCollection(state) != null);
	}
}
